Piece Table

テキストエディタでのテキスト管理実装に使われるアルゴリズム

２つのバッファを持っている

Original buffer

初期のテキストを格納

更新されない

Add buffer

追加されたテキストを格納

Piece

テキストの断片

Bufferの中にあるテキストの断片を指す

Piece Table はこれらのPieceの情報を保持する

Columns

どちらのバッファにあるか（Original/Add）

バッファ内での位置

該当Pieceの開始位置

Pieceの長さ

基本操作

Index

Piece Table を上から見ていってlengthを足していき、i番目が該当するエントリを見つける

Piece Table の情報から、バッファを見に行って取得する

Insert

Add Bufferにテキストを追加し、Piece Tableにも対応する情報を追加する

Delete

1. Piece entryの先頭にあたる文字を削除の場合

Piece Tableのposition, lengthを更新する

e.g, position+1, length-1

2. Piece entryの中にある文字を削除する場合

該当entryを分割（後ろ側Pieceの先頭が削除対象文字になるように）

Piece Tableを更新（1. と同様）

応用操作？

Concatenation？

Pros/Cons

Pros

Cons

実例

VS Code

Atom

気になったこと

Insertとかだけ見てると履歴復元やりやすそうに見えるけど、Deleteも入るとそんな感じはしない。実際のエディタだと履歴はどうやって保持する実装が一般的なんだろう？あんまり関係ないか

関連